Teoria dei numeri

Massimo comune divisore

Il Massimo Comune Divisore (MCD) di due numeri interi a e b, con a ≠ 0 o b ≠ 0 , è il numero naturale più grande per il quale possono entrambi essere divisi.

• Se a = 0 ∧ b ≠ 0, allora MCD(a, b) = b;
• Se a ≠ 0 ∧ b = 0, allora MCD(a, b) = a;
• Se a = 0 ∧ b = 0, allora MCD(a, b) = 0;

Due interi a e b si dicono coprimi tra loro se MCD(a, b) = 1.
Un numero naturale N si dice primo se, per ogni n tale che 1 ≤ n < N, si ha MCD(n, N) = 1.

Algoritmo delle divisioni successive

Il Massimo Comune Divisore di a e b è l'ultimo resto non nullo della sequenza di divisioni.

Minimo comune multiplo

In matematica il Minimo Comune Multiplo (mcm) di due numeri interi a e b è il più piccolo intero positivo multiplo sia di a che di b .
Il mcm gode della proprietà seguente: mcm(a, b) = (a×b)/MCD(a, b).

• Se a = 0 ∨ b = 0, allora mcm (a, b) = 0.

Crivello di Eratostene

Il Crivello di Eratostene è un algoritmo risalente al III secolo a.C. e prende il nome dal suo ideatore, Eratostene di Cirene. Pur essendo molto antico, è ancora oggi molto utilizzato a livello matematico e informatico per la sua semplicità di implementazione.

Dato un intero positivo N, l'algoritmo calcola i numeri primi minori o uguali ad esso nel seguente modo:

• Partendo da i = 2, scarta tutti i suoi multipli fino a N; al termine del ciclo si incrementa la i di 1;
• Per ogni i minore di √(N), se non è già stato eliminato tale valore, si esegue la ricerca e l'eliminazione dei multipli;
• I numeri superstiti sono i numeri primi minori o uguali a N.

Andamento crescente del grafico dei numeri primi per i primi 100 numeri.

GUIDA: inserisci un numero naturale maggiore di 1, quindi premi Crea Tabella per generare la tabella. Premi Calcola per avviare la ricerca dei numeri primi minori o uguali al valore inserito.
I numeri evidenziati in verde compongono il risultato.

Funzione di Eulero

La Funzione di Eulero, che prende il nome dal matematico svizzero Leonardo Eulero vissuto nel XVIII secolo d.C., definisce il numero di interi compresi tra 1 e N che sono coprimi con N.
La funzione φ di Eulero è moltiplicativa per i numeri coprimi tra loro, cioè se a e b sono coprimi allora φ(ab) = φ(a)φ(b).
Inoltre vale che se p è un numero primo allora φ(pⁿ) = (p - 1)×p^{(n - 1)} (per n > 0), mentre per definizione φ(1) = 1.
Queste due regole, insieme al Teorema Fondamentale dell'Aritmetica che dice che ogni numero è un prodotto di numeri primi, ci permettono di calcolare la funzione di Eulero di ogni numero.

Andamento non monotono del grafico della funzione di Eulero per i primi 50 e 2000 valori.

GUIDA: inserisci un numero naturale maggiore di 1, quindi premi Crea Tabella per generare la tabella. Premi Calcola per avviare la ricerca dei numeri coprimi minori del valore inserito.
I numeri evidenziati in verde compongono il risultato.

Creato da Maurizio Gino Nolli